'''
连接两个已经排序好的整数列表，
连接之后的结果仍旧是排序的。

               vR1
list1 = [1, 5, 8]
               vR2
list2 = [0, 3, 9]

list1 会多出 list2 这么多个元素进来，只不过我们不知道 list2 的元素合并进来之后的位置。

       vR2
list2 = [0, 3, 9]
       vR1
list1 = [0, 1, 3, 0, 0, 0]
                        ^Pos

R1 / R2 各自指向 list1 和 list2 各自最大值的位置
Pos 指向扩容之后的列表的最后一个位置，理论上，这个位置应该是合并之后最大值的位置。

Merge l2 into l1 in sorted order.
'''
# 阶段1: 扩容 l1
# 阶段2: 设置标记
# 阶段3: 从右向左填充 l1
# 阶段4: 向 l1 中填充 l2 可能的剩余元素
def merge_sorted(l1: list[int], l2: list[int]):
    # 我们要定义三个位置，分别是 l1 的末尾，l2 的末尾和合并之后的末尾
    r1 = len(l1) - 1
    r2 = len(l2) - 1

    # 定义 l2 元素个数个 0
    zeros = [0] * len(l2)
    l1.extend(zeros)

    pos = len(l1) - 1

    # 从右向左决定 l1 每一个位置的值
    while r1 >= 0 and r2 >= 0:
        if l1[r1] >= l2[r2]:
            l1[pos] = l1[r1]
            r1 -= 1
        else:
            l1[pos] = l2[r2]
            r2 -= 1
        pos -= 1
    
    # 我们还要在 l1 里，继续填充 l2 剩余的元素
    while r2 >= 0:
        l1[pos] = l2[r2]
        r2 -= 1
        pos -= 1

list1 = [1, 5, 8]
list2 = [0, 3, 9]
merge_sorted(l1 = list1, l2 = list2)
print(list1) 
# [1, 5, 8, 0, 0, 0]
# [1, 1, 3, 5, 8, 9]